package com.example.interview.algorithm;

/**
 * 斐波那契数列,第三项等于前两项的和
 * 
 * @Description: TODO
 * @author gaobing
 * @date 2018年9月29日 下午3:48:14 写一个函数，输入n，求斐波那契（Fibonacci) 数列的第n项
 */
public class Test09Fibonacci {

	/**
	 * 1 1 2 3 5 8 13 ...
	 * @param n
	 * @return
	 */
	public static long digui(int n) {
		//F(n)=F(n-1)+F(n-2)
		if (n<=0) {
			return 0;
		}
		if (n==1||n==2) {
			return 1;
		}
		return digui(n-2)+digui(n-1);
	}
	
	/**
	 * 1 1 2 3 5 8 13 ...
	 * 
	 * @param n
	 * @return 第n项的结果
	 */
	public static long fibonacci(int n) {
		if (n <= 0) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		// 否则 n>=3

		// 记录（第n-2个）的斐波那契数列的值
		long prePre = 1;
		// 记录（第n-1个）的斐波那契数列的值
		long pre = 1;
		// 记录（第n个）的斐波那契数列的值
		long current = 2;

		// 求解第n个斐波那契数列的值
		for (int i = 3; i <= n; i++) {
			// 求第i个斐波那契数量的值
			current = pre + prePre;
			// 向前移动，把n-2向前移动一位，即n-1的值
			prePre = pre;
			// 把当前值赋给n-1
			pre = current;
		}
		return current;
	}

	public static void main(String[] args) {
//		System.out.println(fibonacci(0));
//		System.out.println(fibonacci(1));
//		System.out.println(fibonacci(2));
//		System.out.println(fibonacci(3));
//		System.out.println(fibonacci(4));
//		System.out.println(fibonacci(5));
//		System.out.println(fibonacci(6));
//		System.out.println(fibonacci(7));
		System.out.println(digui(7)); 
	}

}
